1. Field of the Invention
This invention relates to computer networks. In particular, the invention relates to route selection.
2. Description of Related Art
One common approach in route selection with bandwidth requirement is to modify the well-known Dijkstra technique so that only links that meet the bandwidth requirement are considered in the Dijkstra procedure. The result is a minimum-cost route over links that can meet the bandwidth requirement.
For example, in a packet forwarding known as Multiprotocol Label Switching (MPLS), to accommodate label switched paths (LSPs) of different priorities, the routing selector may first apply the modified Dijkstra technique based on a given LSP""s bandwidth demand. If a feasible path is not found, the route selector may preempt an existing LSP of lower priority from a congested link in order to re-allocate the bandwidth to the new LSP. A pre-empted LSP will have to be re-established on an alternative route.
This approach has a number of shortcomings. First, it is difficult to make an intelligent decision of which LSP to preempt. The traditional technique is to consider all candidate LSPs on all possible links, evaluate the impact of preempting, and select the LSP that has the minimum cost impact. This is computational expensive and is not practically feasible for large networks. Second, if the preempting is made randomly, a preempted LSP may fail to be re-routed, resulting in loss of connection. Third, the approach disrupts the LSP""s traffic and degrades service quality due to effort in pre-empting and re-routing. Last, the approach may lead to traffic congestion because some high priority LSPs may be placed on very long routes.
Therefore there is a need in the technology to provide a simple and efficient method to select routes in a system of networks.
The present invention is a method and apparatus for selecting a route for a flow from a plurality of network paths. Cumulative costs for a plurality of candidate paths from the network paths are determined using a cost bias which is dynamically calculated based on at least one of a flow attribute and a path attribute. An optimal path is then selected which has a minimum of the cumulative costs. The optimal path corresponds to the selected route.
According to one embodiment of the present invention, the flow attribute includes a flow priority and a bandwidth demand, and the path attribute includes a link bandwidth and a maximum available link bandwidth. The cumulative cost for a candidate node in a candidate path includes a current cumulative cost and a biased static cost. The biased static cost includes a static cost of the link biased by a bias value. The bias value is a function of the flow priority, the bandwidth demand, the link bandwidth, and the maximum available link bandwidth.
The advantages of the present invention include increased traffic efficiency by taking into account bandwidth and traffic requirements in route selection.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.